package leetcode.hash;

public class ManacherCopy {
    public static int Manacher(String s){
       if (s == null && s.length() == 0){
           return 0;
       }
       char[] chars = s.toCharArray();
       char[] chars1 = ManacherString(chars);
       int R = -1;
       int C = -1;
       int[] arr = new int[chars1.length];
       int max = Integer.MIN_VALUE;
        for (int i = 0; i < chars1.length; i++) {

            arr[i] = R>i ? Math.min(R-i,arr[2*C-i]) : 1;

            while (arr[i] + i < chars1.length && i-arr[i]>-1){
                if (chars1[arr[i]]+ 1 == chars1[i-arr[i]]){
                    arr[i]++;
                }else {
                    break;
                }
            }
            if (i + arr[i] > R) { // 更新R和C
                R = i + arr[i];
                C = i;
            }
            max = Math.max(arr[i],max);
        }
        return max-1;
    }
    public static char[] ManacherString(char[] chars){
        char[] chars1 = new char[chars.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < chars1.length; i++) {
            chars1[i] = (i & 1) == 0 ? '#' : chars[index++];
        }
        return chars1;
    }
}